package com.ljy.my_study.lintcode.最大子数组II;

import java.util.Arrays;
import java.util.List;

/** 
* @author James
* @date 2018年10月16日 
*/
public class TestMain {
//	描述
//	给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
//	每个子数组的数字在数组中的位置应该是连续的。
//	返回最大的和。
//
//	子数组最少包含一个数
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出数组 [1, 3, -1, 2, -1, 2]
//	这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7
//
//	挑战
//	要求时间复杂度为 O(n)
	public static void main(String[] args) {
		System.out.println(maxTwoSubArrays(Arrays.asList( 37, 90, 40, 73, 80, 12, 84, -2, 43, 82, 31, 91, -32, -5, 23, 48, 37,
				-32, 42, 42, 12, 59, 46, 99, 30, 3, -39, 31, 48, 26, -1, -22, 49, 20, -1, 72, 92, 70, -26, 8, 29, 11,
				-39, 92, 25, 80, 78, 5, -46, -28, 35, -15, -26, 9, 1, -23, 55, 94, 47, 6, 57, 67, 93, -12, 87, 47, -12,
				-29, -7, -48, 2, 11, 46, 1, -50, 59, 39, -38, 28, 97, 60, 0, 29, 75, 71, 57, 15, 66, 1, 8, -22, 23, 19,
				35, 48, 50, 95, 59 )));
	}
	
	public static int maxTwoSubArrays(List<Integer> nums) {
		Integer[] array=nums.toArray(new Integer[] {});
		int[][] arrays=myMaxSubArray(array);
		int[] result=null;
		int sum=0;
		for(int i=0;i<arrays.length;i++) {
			for(int j=1;j<arrays[0].length;j++) {
				int[] r=new int[4];
				r[0]=i;
				r[1]=j;
				int num=getMax(arrays,i,j,r);
				if(arrays[i][j]+num>=sum) {
					sum=arrays[i][j]+num;
					result=r;
				}
			}
		}
//		System.out.println("subArrays:"+(result[1]-result[0])+"~"+result[1]+","+arrays[result[0]][result[1]]+","+(result[3]-result[2])+"~"+result[3]+","+arrays[result[2]][result[3]]);
		return sum;
	}
	
	public static int getMax(int[][] arrays,int m,int n,int[] result) {
		int max=0;
		int start=n-m<0?0:n-m;
		int end=n;
		for(int i=0;i<arrays.length;i++) {
			for(int j=1;j<arrays[0].length;j++) {
				if(j<start||j-i>end) {
					if(max<=arrays[i][j]) {
						max=arrays[i][j];
						result[2]=i;
						result[3]=j;
					}
				}
			}
		}
		return max;
	}
	
	public static int[][] myMaxSubArray(Integer[] array) {
		int arrLen=array.length;
		int[][] arrays=new int[arrLen+1][arrLen+1];
		int sum=0;
		int[] end= {0,0};
		for(int i=0;i<arrLen;i++) {
			arrays[0][i]=array[i];
			if(sum<array[i]) {
				sum=array[i];
				end[1]=i;
			}
		}
		for(int i=1;i<arrLen+1;i++) {
			for(int j=1;j<arrLen+1;j++) {
				arrays[i][j]=arrays[i-1][j-1]+arrays[0][j];
				if(sum<arrays[i][j]) {
					sum=arrays[i][j];
					end[0]=i;
					end[1]=j;
				}
			}
		}
//		for(int i=0;i<arrLen+1;i++) {
//			for(int j=0;j<arrLen+1;j++) {
//				System.out.print(arrays[i][j]+"	");
//			}
//			System.out.println();
//		}
//		System.out.println("sum:"+sum);
		return arrays;
	}
}
